package Leetcode.树;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: kirito
 * @Date: 2024/3/31 13:04
 * @Description:
 * 验证二叉树的前序序列化
 *
 * 序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
 *
 *
 *
 * 例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
 *
 * 给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
 *
 * 保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
 *
 * 你可以认为输入格式总是有效的
 *
 * 例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
 * 注意：不允许重建树。
 *
 *
 *
 * 示例 1:
 *
 * 输入: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
 * 输出: true
 * 示例 2:
 *
 * 输入: preorder = "1,#"
 * 输出: false
 * 示例 3:
 *
 * 输入: preorder = "9,#,#,1"
 * 输出: false
 *
 *
 * 提示:
 *
 * 1 <= preorder.length <= 104
 * preorder 由以逗号 “，” 分隔的 [0,100] 范围内的整数和 “#” 组成
 */

public class isValidSerialization {
    /**
     * 初始化一个栈，用于存储每个节点的度数。根节点的度数为1，因此初始化时将1压入栈中。
     * 遍历整个前序序列。
     * 如果遇到逗号’,'，则跳过。
     * 如果遇到’#'，表示当前节点为空节点。弹出栈顶元素，表示当前节点消耗了一个度。
     * 如果弹出的度数大于0，说明当前节点还有子节点未处理，将剩余的度数再次压入栈中。
     * 如果遇到数字，表示当前节点的度。弹出栈顶元素，表示当前节点消耗了一个度。
     * 如果弹出的度数大于0，说明当前节点还有子节点未处理，将剩余的度数再次压入栈中。然后将当前节点的度（度数为2）压入栈中。
     * 遍历结束后，如果栈为空，表示所有节点都匹配成功，序列合法；否则，表示序列不合法。
     * @param preorder
     * @return
     */
    public boolean isValidSerialization(String preorder) {
        // 预先定义节点的度为2，即每个节点最多有两个子节点
        int n = preorder.length();
        int i = 0;
        // 使用LinkedList实现Deque接口，用于模拟递归过程中的栈
        Deque<Integer> stack = new LinkedList<Integer>();
        // 初始化栈，根节点度为1
        stack.push(1);
        while (i < n) {
            if (stack.isEmpty()) {
                // 如果栈为空，表示序列不合法
                return false;
            }
            if (preorder.charAt(i) == ',') {
                // 遇到逗号，直接跳过
                i++;
            } else if (preorder.charAt(i) == '#'){
                // 遇到#，表示当前节点为空节点
                // 弹出栈顶元素，表示当前节点消耗了一个度
                int top = stack.pop() - 1;
                // 如果弹出的度数大于0，说明还有子节点未处理
                if (top > 0) {
                    // 将剩余的度数再次压入栈中
                    stack.push(top);
                }
                i++;
            } else {
                // 读取一个数字，表示当前节点的度
                while (i < n && preorder.charAt(i) != ',') {
                    i++;
                }
                // 弹出栈顶元素，表示当前节点消耗了一个度
                int top = stack.pop() - 1;
                // 如果弹出的度数大于0，说明还有子节点未处理
                if (top > 0) {
                    // 将剩余的度数再次压入栈中
                    stack.push(top);
                }
                // 将当前节点的度压入栈中
                stack.push(2);
            }
        }
        // 如果栈为空，表示所有节点都匹配成功，序列合法
        return stack.isEmpty();
    }

    public boolean isValidSerialization2(String preorder) {
        // 获取序列的长度
        int n = preorder.length();
        // 初始化索引指针
        int i = 0;
        // 初始化空槽位数量，一开始有一个槽位用于根节点
        int slots = 1;
        while (i < n) {
            // 如果槽位用尽，说明无法再添加新的节点，返回false
            if (slots == 0) {
                return false;
            }
            if (preorder.charAt(i) == ',') {
                // 遇到逗号，直接跳过
                i++;
            } else if (preorder.charAt(i) == '#'){
                // 遇到#，表示当前节点为空节点，消耗一个槽位
                slots--;
                i++;
            } else {
                // 读取一个数字，表示当前节点的度
                while (i < n && preorder.charAt(i) != ',') {
                    i++;
                }
                // 读取到的数字表示当前节点的度，减去1（当前节点）加上2（两个子节点）
                // 然后将计算出的槽位增加量加到当前的槽位上
                slots += 2 - 1; // slots = slots - 1 + 2
            }
        }
        // 如果所有节点都正确序列化后，槽位为0，返回true
        return slots == 0;
    }

}
